package arrays;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author pengfei.hpf
 * @date 2020/3/4
 * @verdion 1.0.0
 * 在一排多米诺骨牌中，A[i] 和 B[i] 分别代表第 i 个多米诺骨牌的上半部分和下半部分。（一个多米诺是两个从 1 到 6 的数字同列平铺形成的 —— 该平铺的每一半上都有一个数字。）
 *
 * 我们可以旋转第 i 张多米诺，使得 A[i] 和 B[i] 的值交换。
 *
 * 返回能使 A 中所有值或者 B 中所有值都相同的最小旋转次数。
 *
 * 如果无法做到，返回 -1.
 *
 *  
 *
 * 示例 1：
 *
 *
 *
 * 输入：A = [2,1,2,4,2,2], B = [5,2,6,2,3,2]
 * 输出：2
 * 解释：
 * 图一表示：在我们旋转之前， A 和 B 给出的多米诺牌。
 * 如果我们旋转第二个和第四个多米诺骨牌，我们可以使上面一行中的每个值都等于 2，如图二所示。
 * 示例 2：
 *
 * 输入：A = [3,5,1,2,3], B = [3,6,3,3,4]
 * 输出：-1
 * 解释：
 * 在这种情况下，不可能旋转多米诺牌使一行的值相等。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/minimum-domino-rotations-for-equal-row
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class MinDominoRotations {
    public int minDominoRotations(int[] A, int[] B) {
        if(!valid(A, B) || !valid(B, A)){
            return -1;
        }
        Map<Integer, Integer> countMap = new HashMap<>();
        int m = A.length;
        int n = B.length;
        for(int i = 0; i < A.length; i ++){
            int count = 1;
            if(countMap.containsKey(A[i])){
                count = countMap.get(A[i]) + 1;
            }
            countMap.put(A[i], count);
        }
        for(int i = 0; i < B.length; i ++){
            int count = 1;
            if(countMap.containsKey(B[i])){
                count = countMap.get(B[i]) + 1;
            }
            countMap.put(B[i], count);
        }
        List<Integer> toChange = new ArrayList<>();
        int min = Integer.MAX_VALUE;

        for(Map.Entry<Integer, Integer> entry: countMap.entrySet()){
            if(entry.getValue() >= m || entry.getValue() >= n){
                min = entry.getValue();
                toChange.add(entry.getKey());
            }
        }
        if(min == Integer.MAX_VALUE){
            return -1;
        }
        for(Integer num: toChange){
            int i = 0;
            int change = 0;
            int same = 0;

            boolean canRun = true;
            while(i < m && i < n){
                if(A[i] != num && B[i] != num){
                    canRun = false;
                    break;
                } else {
                    if(A[i] == num && B[i] != num){
                        same ++;
                    } else if(A[i] != num && B[i] == num){
                        change ++;
                    }
                }
                i++;
            }
            if(canRun){
                min = Math.min(min, Math.min(change, same));
            }
        }
        return min  == Integer.MAX_VALUE? -1: min;
    }

    private boolean valid(int[] A, int[] B){
        if(A == null || A.length == 0){
            if(B != null && B.length != 0){
                for(int i = 1 ; i < B.length; i ++){
                    if(B[i] != B[i - 1]){
                        return false;
                    }
                }
            } else {
                return false;
            }
        }
        return true;
    }
}
